package club.xiaojiawei.linkedlist;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/16/22 5:09 PM
 * @question 234. 回文链表
 * @description 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 
 */
public class IsPalindrome234 {

    public static void main(String[] args) {
        IsPalindrome234 test = new IsPalindrome234();
        ListNode root = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(1))));
        boolean result = test.isPalindrome(root);
        System.out.println(result);
    }

    /**
     * 栈
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        ListNode temp = head;
        int count = 0;
        while (temp != null){
            count++;
            temp = temp.next;
        }
        if (count == 1){
            return true;
        }
        int middle = count >> 1;
        temp = head;
        int[] arr = new int[count];
        while (middle > 0){
            arr[--middle] = temp.val;
            temp = temp.next;
        }
        if ((count & 1) == 1){
            temp = temp.next;
        }
        while (temp != null){
            if (temp.val != arr[middle++]){
                return false;
            }
            temp = temp.next;
        }
        return true;
    }

    /**
     * 官方-将值复制到数组中后用双指针法
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     * @param head
     * @return
     */
    public boolean isPalindrome2(ListNode head) {
        List<Integer> vals = new ArrayList<Integer>();
        // 将链表的值复制到数组中
        ListNode currentNode = head;
        while (currentNode != null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }
        // 使用双指针判断是否回文
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }

    private ListNode frontPointer;

    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }

    /**
     * 官方-递归
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     * @param head
     * @return
     */
    public boolean isPalindrome3(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }

    /**
     * 官方-快慢指针
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     * @param head
     * @return
     */
    public boolean isPalindrome4(ListNode head) {
        if (head == null) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 民间-hash(nb)
     * @param head
     * @return
     */
    public boolean isPalindrome5(ListNode head) {
        ListNode t=head;
        int base = 31;
        int left = 0, right = 0, mul = 1;
        while(t != null){
            left = left * base + t.val;
            right = right + mul * t.val;
            mul *= base;
            t = t.next;
        }
        return left == right;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

}
